package com.example.searching_and_sorting;




/**
 * ArrayUnorderedList represents an array implementation of an unordered list.
 *
 * @author Lewis and Chase
 * @version 4.0
 */
public class ArrayUnorderedList<T> extends ArrayList<T> 
         implements UnorderedListADT<T>
{
    /**
     * Creates an empty list using the default capacity.
     */
    public ArrayUnorderedList()
    {
        super();
    }

    /**
     * Creates an empty list using the specified capacity.
     *
     * @param initialCapacity the intial size of the list
     */
    public ArrayUnorderedList(int initialCapacity)
    {
        super(initialCapacity);
    }

    /**
     * Adds the specified element to the front of this list.
     * 
     * @param element the element to be added to the front of the list
     */
    @Override
    public void addToFront(T element)
    {
        // To be completed as a Programming seatwork
        if (size() == list.length) {
            expandCapacity();
        }
        int scan = 0;
        //  向下移动一个元素
        for (int shift=rear; shift > scan; shift--) {
            list[shift-1] = list[shift];
        }
        list[0]=element;
        rear++;
        modCount++;

    }

    /**
     * Adds the specified element to the rear of this list.
     *
     * @param element the element to be added to the list
     */
    @Override
    public void addToRear(T element)
    {
        // To be completed as a Programming seatwork
        list[rear] = element;
        rear++;
        modCount++;
    }

    /**
     * Adds the specified element after the specified target element.
     * Throws an ElementNotFoundException if the target is not found.
     *
     * @param element the element to be added after the target element
     * @param target  the target that the element is to be added after
     */
    @Override
    public void addAfter(T element, T target)
    {
        if (size() == list.length) {
            expandCapacity();
        }

        int scan = 0;
		
		// find the insertion point
        while (scan < rear && !target.equals(list[scan])) {
            scan++;
        }
      
        if (scan == rear) {
            throw new ElementNotFoundException("UnorderedList");
        }
    
        scan++;
		
		// shift elements up one
        for (int shift=rear; shift > scan; shift--) {
            list[shift] = list[shift-1];
        }

		// insert element
		list[scan] = element;
        rear++;
		modCount++;
    }

    public static void main(String[] args) {
        ArrayUnorderedList arrayUnorderedList = new ArrayUnorderedList();
        arrayUnorderedList.addToFront(20172301);
        arrayUnorderedList.addToRear(20172303);
        arrayUnorderedList.addToRear(20172309);
        arrayUnorderedList.addToRear(20172305);
        arrayUnorderedList.addToRear(20172308);
        arrayUnorderedList.addToRear(20172302);
        arrayUnorderedList.addToRear(20172306);
        arrayUnorderedList.addToRear(20172307);
        arrayUnorderedList.addToRear(20172304);


        System.out.println("Is the ordered list empty? ");
        System.out.println(arrayUnorderedList.isEmpty());
        System.out.println("The elements in an unordered list are:  " );
        System.out.println(arrayUnorderedList);
        System.out.println("After the element of the unordered list is inserted into 20172302, the list element are:  ");
        arrayUnorderedList.addAfter(20172301,20172302);
        System.out.println(arrayUnorderedList);
        System.out.println("The first element in an unordered list is:  ");
        System.out.println(arrayUnorderedList.first());
        System.out.println("The last element in an unordered list is:  ");
        System.out.println(arrayUnorderedList.last());

        System.out.println("Look for elements in an ordered list 20172305:");
        System.out.println(arrayUnorderedList.find(20172305));
        System.out.println("The element in the ordered list after deleting the specified element(20172305) are  ");
        arrayUnorderedList.remove(20172305);
        System.out.println(arrayUnorderedList);
        System.out.println("The number of elements in an ordered list is:   ");
        System.out.println(arrayUnorderedList.size());
        System.out.println("The element in the ordered list after deleting the header element are:  " );
        arrayUnorderedList.removeFirst();
        System.out.println(arrayUnorderedList);
        System.out.println("The element in the ordered list after deleting the last position element are:  " );
        arrayUnorderedList.removeLast();
        System.out.println(arrayUnorderedList);

    }
}
